import java.util.Arrays;

/**
 * @author CHENTAIWEN
 * @create 2022/9/20 16:59
 */
public class MyKMP {
    public static void main(String[] args) {

        String t = "whosyourdaddy";
        String p = "your";
        if (isKMP(t, p)) {
            System.out.println("包含");
        } else {
            System.out.println("不包含");
        }
    }

    public static boolean isKMP(String str1, String str2) {
        int t = str1.length();
        int p = str2.length();
        boolean flag = false;
        int[] next = getNext(str2);
        System.out.println(Arrays.toString(next));
        if (t > p) {
            int k = -1;
            for (int i = 0; i < t; i++) {
                while (k > -1 && str1.charAt(i) != str2.charAt(k + 1)) {
                    k = next[k];
                }
                if (str1.charAt(i) == str2.charAt(k + 1)) {
                    k++;
                    if (k == p - 1) {
                        return true;
                    }
                }
            }
        }

        return flag;
    }

    //先自己进行重复比较进行
    public static int[] getNext(String p) {
        int[] next = new int[p.length()];
        next[0] = -1;
        int k = -1;
        for (int i = 1; i < p.length(); i++) {
            while (k > -1 && p.charAt(i) != p.charAt(k + 1)) {
                k = next[k];
            }
            if (p.charAt(i) == p.charAt(k + 1)) {
                k = k + 1;
            }
            next[i] = k;
        }
        return next;
    }
}
